package com.person.leetcode.editor.cn;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 15.三数之和
 * 2022-05-20 09:55:17
 **/
public class Sequence_0015_ThreeSum {
    public static void main(String[] args) {
        Solution solution = new Sequence_0015_ThreeSum().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    //-4 -1 -1 0 1 2
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            ArrayList<List<Integer>> ans = new ArrayList<>();
            int a = 0, b, c;
            for (; a < nums.length - 2 && nums[a] <= 0; a++) {
                if (a > 0 && nums[a] == nums[a - 1]) {
                    continue;
                }
                for (b = a + 1; b < nums.length - 1 && nums[a] + nums[b] <= 0; b++) {

                    if (b > a+1 && nums[b] == nums[b - 1]) {
                        continue;
                    }
                    for (c = nums.length - 1; c > b && nums[a] + nums[b] + nums[c] >= 0; c--) {
                        if (c < nums.length - 1 && nums[c] == nums[c + 1]) {
                            continue;
                        }
                        if (nums[a] + nums[b] + nums[c] == 0) {
                            ans.add(new ArrayList<>(Arrays.asList(nums[a] , nums[b] ,nums[c])));
                            break;
                        }
                    }
                }
            }

            return ans;
        }
//            Arrays.sort(nums);
//            int len = nums.length;
//            List<List<Integer>> ans = new ArrayList<>();
//            // a < b < c
//            int a = 0, b, c;
//            for (; a < len - 2; a++) {
//                if (a > 0 && nums[a] == nums[a - 1]) {
//                    continue;
//                }
//                for (b = a + 1; b < len - 1; b++) {
//                    if (b - 1 > a && nums[b] == nums[b - 1]) {
//                        continue;
//                    }
//                    for (c = len - 1; c > b && nums[a] + nums[b] + nums[c] >= 0; c--) {
//                        if (nums[a] + nums[b] + nums[c] == 0) {
//                            ans.add(Arrays.asList(nums[a],nums[b],nums[c]));
//                            break;
//                        }
//                    }
//                }
//            }
//            return ans;
//        }
//
//        public List<List<Integer>> tthreeSum(int[] nums) {
//            int n = nums.length;
//            Arrays.sort(nums);
//            List<List<Integer>> ans = new ArrayList<List<Integer>>();
//            // 枚举 a
//            for (int first = 0; first < n; ++first) {
//                // 需要和上一次枚举的数不相同
//                if (first > 0 && nums[first] == nums[first - 1]) {
//                    continue;
//                }
//                // c 对应的指针初始指向数组的最右端
//                int third = n - 1;
//                int target = -nums[first];
//                // 枚举 b
//                for (int second = first + 1; second < n; ++second) {
//                    // 需要和上一次枚举的数不相同
//                    if (second > first + 1 && nums[second] == nums[second - 1]) {
//                        continue;
//                    }
//                    // 需要保证 b 的指针在 c 的指针的左侧
//                    while (second < third && nums[second] + nums[third] > target) {
//                        --third;
//                    }
//                    // 如果指针重合，随着 b 后续的增加
//                    // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
//                    if (second == third) {
//                        break;
//                    }
//                    if (nums[second] + nums[third] == target) {
//                        List<Integer> list = new ArrayList<Integer>();
//                        list.add(nums[first]);
//                        list.add(nums[second]);
//                        list.add(nums[third]);
//                        ans.add(list);
//                    }
//                }
//            }
//            return ans;
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
